This invention relates generally to network switches and, more specifically, to an improved look up mechanism and associated multi-page hash table used for improved performance in retrieving information and making forwarding decisions in a network switch.
A network switch of a data communications network provides a xe2x80x9cswitching functionxe2x80x9d for transferring information, such as data frames, among entities of the network. Typically, the switch is a computer comprising a collection of components (e.g., cards) interconnected by a backplane of wires. Each card may include a limited number of ports that couple the switch to the other network entities over various types of media, such Ethernet, FDDI or token ring connections. A network entity may consist of any device that xe2x80x9csourcesxe2x80x9d (i.e., transmits) or xe2x80x9csinksxe2x80x9d (i.e., receives) data frames over such media.
The switching function provided by the switch typically comprises receiving data at a source port from a network entity, transferring the data over the backplane to a destination port and, thereafter, transmitting that data over a medium to another entity of the network. In order for the data to be transferred, the switch may include a forwarding engine and associated address translation mechanism. An example of such an address translation mechanism is described in U.S. Pat. No. 5,740,171, issued Apr. 14, 1998, entitled ADDRESS TRANSLATION MECHANISM FOR A HIGH PERFORMANCE NETWORK SWITCH, which is commonly owned by the assignee of the present invention. The address translation mechanism described therein quickly and efficiently renders forwarding decisions for data frames transported among ports of a high-performance switch on the basis of, inter alia, virtual local area network (VLAN) associations among the ports.
The translation mechanism comprises a plurality of forwarding tables, each of which contains entries having unique index values that translate to selection signals for ports destined to receive the data frames. Each port is associated with a unique index value and a VLAN identifier to facilitate data transfers within the switch at accelerated to speeds and addressing capabilities.
As described in the patent, a media access control (MAC) address is combined with the VLAN identifier to produce a base line numerical quantity for searching the forwarding tables. Each table entry is directly accessed, however, by a key comprising a hash transformation of this MAC/VLAN quantity. A comparison circuit arrangement of is the mechanism is also provided to validate the forwarding table entry mapped by the hashed MAC/VLAN quantity. That is, the circuit arrangement compares the base line numerical quantity to a MAC/VLAN value stored in the mapped entry to ensure that the entry contains the correct index value. If the compared items match, the index value stored in the table is provided to a target logic circuit for translation to a signal that selects a port or group of ports for receiving the data frame. If the items do not match, the VLAN identifier is passed to the target logic circuit with the result that all ports having that VLAN identifier receive the frame in accordance with a multicast transfer.
The hash function used to find the index value maps a large address space with a much smaller address space. In doing so, however, aliasing can occur in that more than one key, for example, a MAC address/VLAN pair, can hash to the same table entry. One solution to this limitation has been to provide a hash table comprising several pages which can be used as alternates when a particular key (e.g., MAC address/VLAN pair) hashes to the same table entry. For example, a first MAC address/VLAN pair may hash to a particular table entry in which case that entry (or line) corresponding to the first page of the table is thereafter associated with that MAC address/VLAN pair. If a second MAC address/VLAN pair hashes to the same value, thus pointing to that same entry, then it is stored in the corresponding entry on the second page of the table.
The problem with this type of paging scheme, however, is that it increases the overall table access time because the hash transformation may not always result in a xe2x80x9chitxe2x80x9d on the first page accessed. Specifically, after the hashed address is calculated, it is used to point to the entry (or line) to access, but the look up always begins on the first page. If a match is not found, the corresponding entry on the second page is checked, and if there is no match this procedure continues through all the pages of the table until a match is realized. In such conventional systems, the order in which pages are accessed, including which page is accessed first, is the same for all hashed addresses. But, serially checking the various pages consumes time, perhaps on the order of several cycles. Optimum performance, namely highest speed, is achieved when the desired entry is found on the first is page checked.
Therefore, it is among the objects of the present invention to provide a mechanism for high-speed look up of hash table information needed for rendering forwarding decisions in a network switch.
Another object of the present invention is to provide a hashing technique which increases the likelihood of accessing desired data upon a first look up of a hash table.
It is a further object of the present invention to provide a mechanism that efficiently implements xe2x80x9cport-basedxe2x80x9d VLAN association operations within a high-performance network switch.
Briefly, the invention relates to an improved look-up mechanism for storing and retrieving forwarding information used to transport data frames among ports of a high-performance network switch. The look-up mechanism includes a look-up table having a multi-page architecture that is accessed in accordance with a novel, dual hashing technique. Broadly stated, the dual hashing technique first assigns a mapping between a first virtual page to the physical page of the look-up table to be initially accessed. Secondly, the hashing technique points to a particular entry (or line) in the table on that identified page. The dual hashing technique is used for both initially storing and for ultimately retrieving information from the look-up table. Use of the technique increases the likelihood that a match will be found on a first look up operation to the table.
In the illustrative embodiment, the hash table is configured as a number of physical pages with each page containing an equal number of entries. Equivalent entries on each page form a line. In accordance with one embodiment of the invention, a single, large hash key is derived from a MAC address/VLAN pair involved in the forwarding decision. The larger hash key is generated to effectively produce two hashes. One set of predetermined bits (e.g., the most significant bits (MSBs)) of the hash key are decoded to obtain a value which designates the mapping between the virtual first page and the physical page to access first for that hash key. The remaining bits in the large hash key are used to identify the particular line on that page in the table to access. Initially, the corresponding forwarding information (i.e., the MAC/VLAN pair and the corresponding index) is stored in that location in the look-up table. In this manner, each time that particular MAC address/VLAN pair subsequently is received by the forwarding engine in a forwarding operation, the same physical location of the look-up table is checked first, and the forwarding index is thus retrieved upon a single access. In an alternative embodiment, two separate hashes can be performed, one may be used to obtain the page-to-page mapping, and the other, to identify the line on the corresponding page.
More specifically, when the forwarding engine receives a frame, it contains a destination address and a source address. The destination address is hashed to obtain the hash key and the virtual first page (VFP) is determined from a predetermined number of bits of the key. That VFP is initially accessed. The remaining bits of the hash key are used to point to a line on that page. If the entry pointed to on that page is valid, it is verified as correct, and if so, then the forwarding information (the index) is retrieved.
If the designated location contains valid information, but the key information does not match the incoming address, then, subsequent pages are to be accessed. When subsequent pages are to be checked, the mapping continues sequentially such that the second page to be accessed is the next sequential physical page after the VFP. In other words, if the virtual first page is mapped to page 3 of the table, then the mapping continues such that the second page to be accessed is page 4, and so on.
The speed of the look-up process can be further increased by using an associated table which contains valid bits to indicate which look up table entries are valid. In this case, only valid entries are checked in the order identified by the page-to-page mapping technique until a match is found. If no match is found after all valid entries on that line are checked, then a miss is declared, and a learning mode of operation is initiated.
During the learning mode of operation, the MAC address/VLAN pair is hashed to obtain the hash key, as described. A predetermined quantity of bits, which may be the MSBs of the key, or the result of a separate hash, are translated to a virtual first page assigned to that MAC address/VLAN pair. The VFP is accessed, and the MAC address/VLAN information (and the associated index) is stored on the line pointed to on that particular page, (assuming the location is empty.) In this way, when the look up engine subsequently receives a frame with that particular MAC address/VLAN pair, the same entry on the same virtual first page is accessed and the forwarding information is thus obtained on the first look up.
On the other hand, if the particular entry is not empty, i.e., other valid information is stored therein (because of a previous hash to the same address), then the MAC address/VLAN information is stored in the same location on the next physical page, or on the next page containing an invalid (available) entry during the learning operation. Most likely, it will only take two or three pages to arrive at an empty entry in which the information can be stored. Thereafter, if that particular MAC address/VLAN pair is received by the forwarding engine as a destination address, and the virtual first page assignment is used to start the look up process, even though the information is not obtained on the first look up, it will be found on the second (or third) access of the table. This approach still reduces the number of total accesses that may have been required in prior systems, thus increasing the high-speed performance of the switch.